import java.util.Random;

public class MergeSorting implements Runnable {
    final int[] arr;
    private final int startPos;
    private final int endPos;
    //------------------------------------------------------------
    public MergeSorting(int[] arr, int startPos, int endPos) {
        this.arr = arr;
        this.startPos = startPos;
        this.endPos = endPos;
    }
    //------------------------------------------------------------
    public void sort(int start, int end) {
        if (end - start <= 1) {
            return;
        }

        int middle = (start + end) / 2;

        Thread th = new Thread(new MergeSorting(arr, start, middle));
        th.start();
        sort(middle, end);

        try {
            th.join();
        } catch (InterruptedException ex) {
            System.out.println(Thread.currentThread() + " interrupted unexpectedly");
            return;
        }

        merge(start, middle, end);
    }
    //--------------------------------------------------------------
    private void merge(int start, int middle, int end) {
        int posLeft = start, posRight = middle;

        while (posLeft != posRight && posRight < end) {
            if (arr[posLeft] > arr[posRight]) {
                int temp = arr[posRight];
                System.arraycopy(arr, posLeft, arr, posLeft + 1, posRight
                        - posLeft);
                arr[posLeft] = temp;
                ++posRight;
            }
            ++posLeft;
        }
    }
    //--------------------------------------------------------------
    @Override
    public void run() {
        sort(startPos, endPos);
    }
    //--------------------------------------------------------------
    public void display(){
        for (int i:arr){
            System.out.println(i + " ");
        }
    }
    //--------------------------------------------------------------
    public static int [] createRandomArray(int size, int range) {
        int [] list = new int[size];
        Random random = new Random(System.currentTimeMillis());
        for (int i = 0; i < size; ++i) {
            list[i] = random.nextInt(range);
        }
        return list;
    }
    //--------------------------------------------------------------
}//End class MergeSorting
